package leetcode.lt100;

class Solution_42 {
	
	public static void main(String[] args) {
		int [] test = {0,1,0,2,1,0,1,3,2,1,2,1};
		new Solution_42().trap(test);
	}
	
	public int trap(int[] height) {

		int l = height.length;

		// 找出最高点坐标
		int maxHeightIndex = 0;
		for (int i = 0; i < l; i++) {
			if (height[i] > height[maxHeightIndex])
				maxHeightIndex = i;
		}

		int res = 0;

		// 分析左半区域
		int leftHeightMax = 0;
		for (int i = 0; i < maxHeightIndex; i++) {
			leftHeightMax = Math.max(leftHeightMax, height[i]);
			res += leftHeightMax - height[i] > 0 ? leftHeightMax - height[i] : 0;
		}

		// 分析右半区域
		int rightHeightMax = 0;
		for (int i = l - 1; i > maxHeightIndex; i--) {
			rightHeightMax = Math.max(rightHeightMax, height[i]);
			res += rightHeightMax - height[i] > 0 ? rightHeightMax - height[i] : 0;
		}

		return res;
	}
}